package leetcode.dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：
 *
 * 在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。
 * 青蛙无法跳回已经访问过的顶点。
 * 如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。
 * 如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。
 * 无向树的边用数组 edges 描述，其中 edges[i] = [fromi, toi] 意味着存在一条直接连通 fromi 和 toi 两个顶点的边。
 *
 * 返回青蛙在 t 秒后位于目标顶点 target 上的概率。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
 * 输出：0.16666666666666666
 * 解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，第 1 秒 有 1/3 的概率跳到顶点 2 ，然后第 2 秒 有 1/2 的概率跳到顶点 4，因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。
 * 示例 2：
 *
 *
 *
 * 输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
 * 输出：0.3333333333333333
 * 解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，有 1/3 = 0.3333333333333333 的概率能够 1 秒 后跳到顶点 7 。
 * 示例 3：
 *
 * 输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
 * 输出：0.16666666666666666
 *  
 *
 * 提示：
 *
 * 1 <= n <= 100
 * edges.length == n-1
 * edges[i].length == 2
 * 1 <= edges[i][0], edges[i][1] <= n
 * 1 <= t <= 50
 * 1 <= target <= n
 * 与准确值误差在 10^-5 之内的结果将被判定为正确。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/frog-position-after-t-seconds
 */
public class T秒后青蛙的位置 {

    /**
     *
     * @param n 节点数
     * @param edges 边
     * @param t 跳数
     * @param target 目标
     * @return 概率
     */
    public static double frogPosition(int n, int[][] edges, int t, int target) {
        // 只有一个点 且目的地必须是1
        if (n==1){
            if( target==1)return 1;
            else return 0;
        }
        // 初始化参数
        count = t;
        target1 = target;
        fm = 1;
        // 从1开始 记录各条边 由于是无向的所以需要记录两次
        List[] edge = new List[n+1];
        for (int[] i : edges){
            if (edge[i[0]] == null){
                edge[i[0]] = new ArrayList();
            }
            if (edge[i[1]] == null){
                edge[i[1]] = new ArrayList();
            }
            edge[i[0]].add(i[1]);
            edge[i[1]].add(i[0]);
        }
        // 对边进行标记
        boolean[][] flags = new boolean[n+1][n+1];
        // 未找到则返回0
        if (!dfs(edge, 1, 1, flags)) return 0;
        // 找到则返回概率
        return (double) 1/fm;
    }

    // 分母
    private static int fm = 1;
    // 跳跃次数
    private static int count;
    // 目标
    private static int target1;

    /**
     * dfs
     * @param l 邻接表
     * @param tmp 当前节点
     * @param c 已跳数
     * @param flags 标记
     * @return 找到与否
     */
    private static boolean dfs(List<Integer>[] l, int tmp, int c, boolean[][] flags){
        if (c > count || l[tmp] == null || size(l[tmp],flags,tmp)==0) {return false;}
        else {
            for (Integer i : l[tmp]){
                // 该边已被标记
                if (flags[tmp][i]) continue;
                // 提前标记
                flags[tmp][i] = true;
                flags[i][tmp] = true;
                // 考虑原地跳的要求是没有可以跳的下一节点
                if (i == target1 && (c==count || size(l[i],flags,i)==0)){
                    fm *= size(l[tmp], flags, tmp)+1;
                    return true;
                } else {
                    // 由于一条边已被提前标记所以需要+1补偿
                    int z = size(l[tmp], flags,tmp)+1;
                    fm *= z;
                    if (!dfs(l, i, c+1, flags)){
                        fm /= z;
                    }else {
                        // 找到则结束递归
                        return true;
                    }
                    flags[tmp][i] = false;
                    flags[i][tmp] = false;
                }
            }
        }
        return false;
    }

    /**
     *
     * @param l 下一跳
     * @param a 标记
     * @param tmp 当前节点
     * @return 可跳数
     */
    private static int size(List<Integer> l, boolean[][] a, int tmp){
        int i = 0;
        for (Integer z : l){
            if (!a[z][tmp] && !a[tmp][z]) i++;
        }
        return i;
    }

    public static void main(String[] args){
//        int[][] a = new int[][]{{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
        // [[2,1],[3,1],[4,2],[5,1],[6,2],[7,5],[8,7],[9,7]]
//        int[][] a = new int[][]{{1,2},{1,3},{4,2},{5,1},{2,6},{7,5},{8,7},{9,7}};
        int[][] a = new int[][]{{2,1},{3,2}};
        System.out.println(frogPosition(3,a,16,3));
    }
}
